package com.kobe.game_40;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 
 * A permutation is an ordered arrangement of objects. For example, 3124 is one
 * possible permutation of the digits 1, 2, 3 and 4. If all of the permutations
 * are listed numerically or alphabetically, we call it lexicographic order. The
 * lexicographic permutations of 0, 1 and 2 are:
 * 
 * 012 021 102 120 201 210
 * 
 * What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4,
 * 5, 6, 7, 8 and 9?
 * 
 * 
 */

public class Game24 {
    static Map<Integer, Integer> arrangesMap = new HashMap<Integer, Integer>();
    static {
        arrangesMap.put(1, 1);
        arrangesMap.put(2, 2);
        for (int i = 3; i <= 10; i++) {
            arrangesMap.put(i, i * arrangesMap.get(i - 1));
        }
    }

    public static void main(String[] args) {
        int[] result = getLexicographic(1000000);
        for (int temp : result) {
            System.out.print(temp + " ");
        }
    }

    public static int[] getLexicographic(int index) {
        int permutationLenth = 0;
        for (int i = 2; i <= 10; i++) {
            if (arrangesMap.get(i) >= index && arrangesMap.get(i - 1) < index) {
                permutationLenth = i;
                break;
            }
        }
        return caculate(null, index, 0, permutationLenth, null);
    }

    public static int[] caculate(List<Integer> input, int remain, int index,
            int remainLength, int[] container) {
        if (container == null) {
            container = new int[remainLength];
        }
        if (input == null) {
            input = new ArrayList<Integer>();
            for (int i = 0; i < remainLength; i++) {
                input.add(i);
            }
        }
        if (remainLength == 1) {
            container[index] = input.get(0);
            return container;
        }
        int remainBase = arrangesMap.get(remainLength - 1);
        int multiple = remain / remainBase;

        if (remain % remainBase == 0) {
            multiple--;
        }
        remain = remain - multiple * remainBase;
        container[index] = input.get(multiple);
        input.remove(multiple);
        index++;
        remainLength--;
        return caculate(input, remain, index, remainLength, container);
    }
}
